//C07:MultiSet1.cpp
// Demonstration of multiset behavior.
#include <algorithm>
#include <cstdlib>
#include <functional>
#include <iostream>
#include <iterator>
#include <ostream>
#include <set>
using namespace std;

class X
{
    char c;    // Used in comparison
    int i;     // Not used in comparison
    // Don't need default constructor and operator=
    X();
    X& operator=(const X&);
    // Usually need a copy-constructor (but the
    // synthesized version works here)
    public:
        X(char cc, int ii) : c(cc), i(ii) {}
        // Notice no operator== is required
        friend bool operator<(const X& x, const X& y)
        {
            return x.c < y.c;
        }

        friend ostream& operator<<(ostream& os, X x)
        {
            return os << x.c << ":" << x.i;
        }
};

class Xgen
{
    static int i;
    // Number of characters to select from:
    enum { SPAN = 6 };
    public:
        X operator()() 
        {
            char c = 'A' + rand() % SPAN;
            return X(c, i++);
        }
};

int Xgen::i = 0;
typedef multiset<X> Xmset;
typedef Xmset::const_iterator Xmit;

int main(void)
{
    Xmset mset;
    // fill it with X's:
    srand(time(0));
    generate_n(inserter(mset, mset.begin()), 25, Xgen());
    // Initialize a regular set from mset:
    set<X> unique(mset.begin(), mset.end());
    copy(unique.begin(), unique.end(),
        ostream_iterator<X>(cout, " "));
    cout << "\n----------" << endl;
    // Iterator over the unique values:
    for (set<X>::iterator i = unique.begin();
        i != unique.end(); i++)
    {
        pair<Xmit, Xmit> p = mset.equal_range(*i);
        copy(p.first, p.second, ostream_iterator<X>(cout, " "));
        cout << endl;
    }    
}